package Testdemo5;

import  java.lang.*;

import linklist.MyLinkedList.LinkedNode;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-06-04
 * Time：17:09
 */
public class Test1 {


    /**
     * 反转相邻节点
     * @param head 头结点
     * @return 返回反转后的节点
     *
     */

    public LinkedNode swapPairs(LinkedNode head) {
        // 递归的出口
        if(head==null || head.next==null ) {
            return head;
        }

        LinkedNode ret = head.next;
        // 得到新的节点
        LinkedNode node = swapPairs(head.next.next);

        // 将前面两个节点和后面部分节点进行连接
        head.next.next=head;
        head.next=node;

        return ret;
    }

    public static void main1(String[] args) {
        System.out.println(myPow(2.00, -2147483648));
    }

    /**
     * 指数幂
     * @param x
     * @param n
     * @return
     */



//    public static double myPow(double x, int n) {
//        // 判断 n 的正负
//        return n < 0 ? 1.0/dfs(x,-n) : dfs(x,n);
//    }
//
//    public static double dfs(double x,int n) {
//        // 边界条件
//        if(n==0) {
//            return 1;
//
//        }
//
//        // 先得到一半的值
//        double sum = dfs(x, n/2);
//
//        // 判断是奇偶
//        return n%2==0 ? sum*sum : sum*sum *x;
//    }


    /**
     * 指数幂
     * 拆分一半的思想
     * 得到指数的一半的值
     *
     * 进行相乘即可
     *
     *
     * @param x 底数
     * @param n 指数
     * @return 返回结果
     */

    public static double myPow(double x, int n) {
        // 判断n的正负

        /**
         *
         *   如果是负整数指数幂
         *    有可能会超出 int 的范围 需要强转
         *    这里不要传负数
         *   Java中 负数取模是相反的
         *
         */


        if(n < 0 ) return  1.0/ dfs(x,-(long)n);

        return dfs(x,n);
    }


    public static double dfs(double x,long n) {
        // 判断递归出口
        if(n==0) {
            return 1;
        }

        // 方法体的书写

        // 先得到一半次方的数
        double bin =  dfs(x,n/2);

        if(n%2==1) {
            // 判断是奇数次方
            // 需要多乘一次 自身的数字
            return bin * bin * x;
        } else {
            // 偶次方的话
            // 只需要两个一半次方数相乘即可

            return  bin* bin;
        }

    }

    /**
     * 计算布尔二叉树的值
     * @param root 根节点
     * @return 返回布尔值
     */

    public boolean evaluateTree(TreeNode root) {
        return  dfs(root)==1 ? true : false;
    }


    public int  dfs(TreeNode root) {
        // 如果这个节点为叶子节点

        if(root.left==null && root.right==null) {
            return root.val;
        }

        //  分别得到左右子树的节点
        int leftval = dfs(root.left);
        int rightval = dfs(root.right);


        // 进行判断返回
        if(root.val==2) {
            // 当前值为 val
            if(leftval==1 || rightval==1 ) {
                return 1;
            } else {
            // 当前值为 0
                return 0;
            }
        } else {
            // 另外情况
            if(leftval==0 || rightval==0 ) {
                return 0;
            } else {
                return 1;
            }
        }
    }


//    public static void main(String[] args) {
//        int x = 1;
//        int y = 2;
//        int z = 3;
////        Math.
////        int c = x + Math.pow()
//
//    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode node = new TreeNode(1);

        root.left= node;
        System.out.println(sumNumbers(root));
    }


//    public static int sumNumbers(TreeNode root) {
//
//        // 调用
//        return dfs(root,root.val);
//    }
//
//    public static int dfs (TreeNode root , int num) {
//        // 递归出口
//        // 特殊情况考虑
//        if(root.left == null ) {
//            return num;
//        }
//
//        int leftval =  dfs(root.left,num*10 + root.left.val) ;
//
//
//        if(root.right == null) {
//            return leftval;
//        }
//
//
//        int rightval = dfs(root.right,num*10 + root.right.val);
//
//
//        return leftval+ rightval;
//
//    }


    /**
     * 求根节点到叶子节点数之和
     * @param root
     * @return
     */

    public static int sumNumbers(TreeNode root) {
        // 调用
        return dfs(root,root.val);
    }

    public static int dfs (TreeNode root , int num) {
        // 递归出口
        // 特殊情况考虑
        if(root.left==null && root.right==null) {
            return num;
        }


        /**
         *
         *  利用参数向下传递
         *
         * 并相信dfs一定能帮我得到左子树的值
         *
         */

        int leftval = 0;
        if(root.left != null) {
            leftval =  dfs(root.left,num*10 + root.left.val) ;
        }

        int rightval = 0;


        if(root.right != null) {
            rightval = dfs(root.right,num*10 + root.right.val) ;
        }



        return leftval+ rightval;

    }


    /**
     * 二叉树剪枝
     * 判断叶子节点
     * 当出现左右为0 自身也为0 的部分全部剪掉
     *
     * 利用后序遍历
     * 返回当前的值
     *
     *
     * 函数头：
     * root根节点
     *
     * 函数体：
     * 后序遍历
     * 判断左右两边是否为null
     * 再判断自身是否为 0
     * 就返回null
     * 否则就连接左右节点
     *
     * 返回值：
     * 返回当前节点
     *
     * 递归出口：
     * root=null
     *
     */

        public TreeNode pruneTree(TreeNode root) {
            return   dfs1(root);
        }

        public static TreeNode dfs1(TreeNode root) {
            // 处理为null的情况
            if(root==null) {
                return null;
            }


            // 处理左子树
            TreeNode leftNode = dfs1(root.left);
            // 处理右子树
            TreeNode rightNode = dfs1(root.right);

            // 是否左右为null 并且自身等于 0 的情况
            if(leftNode==null && rightNode==null && root.val==0) {
                return null;
            }

            // 进行连接
            root.left=leftNode;
            root.right=rightNode;

            return root;
        }


    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */


    /**
     * 计算布尔二叉树的值
     *
     * 思路：
     * 先判断叶子节点是 0 还是 1
     * 然后再判断非叶子节点是 3还是4
     *
     *
     * 函数头：
     * root根节点
     *
     * 函数体：
     * 先后序遍历
     * 判断叶子节点
     * 再判断非叶子节点
     *
     * 返回值：
     * 布尔类型
     *
     * 递归出口：
     * root=null
     *
     * @param root
     * @return
     */

        public boolean evaluateTree1(TreeNode root) {
            return  dfs2(root);
        }

        public static boolean dfs2(TreeNode root) {
            // 特殊情况
            // 节点为null返回false
            if(root==null) {
                return false;
            }

            // 如果为叶子树进行判断
            if(root.left == null && root.right == null) {
                if(root.val==1) {
                    return true;
                } else{

                    return false;
                }
            }

            // 遍历左子树
            boolean leftBool = dfs2(root.left);
            // 遍历右子树
            boolean rightBool = dfs2(root.right);


            // 返回逻辑判断
            if(root.val==2) {
                return leftBool||rightBool;
            } else {
                return leftBool && rightBool;
            }




        }


}
